package week5;

import java.util.Arrays;

/**
 *
 * 1011. 在 D 天内送达包裹的能力
 * https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：15 ms, 在所有 Java 提交中击败了31.56% 的用户
 * 内存消耗：41.6 MB, 在所有 Java 提交中击败了47.29% 的用户
 * 通过测试用例：85 / 85
 * 炫耀一下:
 *
 *
 */
public class Week5CapacityToShipPackagesWithinDDays {

    public int shipWithinDays(int[] weights, int days) {
        int left = Arrays.stream(weights).max().getAsInt();
        int right = Arrays.stream(weights).sum();
        for(;left < right;) {
            int middle = (left + right) / 2;
            int need = 1;
            int cur = 0;
            for(int weight : weights) {
                if(cur + weight > middle) {
                    need++;
                    cur = 0;
                }
                cur += weight;
            }
            if(need <= days) {
                right = middle;
            } else {
                left = middle + 1;
            }
        }

        return left;
    }
}
